package week6;

import java.util.List;

/**
 *
 * 120. 三角形最小路径和
 * https://leetcode-cn.com/problems/triangle/
 *
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：3 ms, 在所有 Java 提交中击败了73.14% 的用户
 * 内存消耗：38.2 MB, 在所有 Java 提交中击败了51.95% 的用户
 * 通过测试用例：44 / 44
 * 炫耀一下:
 *
 *
 */
public class Week6Triangle {

    public int minimumTotal(List<List<Integer>> triangle) {
        int triangLength = triangle.size();
        int[] array = new int[triangLength];
        array[0] = triangle.get(0).get(0);
        for(int f1 = 1; f1 < triangLength; f1++) {
            array[f1] = array[f1 -1] + triangle.get(f1).get(f1);
            for(int f2 = f1 - 1; f2 > 0; f2--) {
                array[f2] = Math.min(array[f2 - 1], array[f2]) + triangle.get(f1).get(f2);
            }
            array[0] += triangle.get(f1).get(0);
        }

        int minTotal = array[0];
        for(int size = 1; size < triangLength; size++) {
            minTotal = Math.min(minTotal, array[size]);
        }
        return minTotal;
    }
}
